#include <stdio.h>
#include <stdlib.h>

/*
 * 迪杰斯特拉：单源点最短路径
 */

#define max 32767
#define vertex 5
#define edge 9

struct graph
{
  int arcs[vertex+1][vertex+1];	// 图的邻接矩阵
  int dist[vertex+1];		// 存放从源点到各顶点的最短路径
  int path[vertex+1];	// 存放在最短路径上该顶点的前一顶点号
  int s[vertex+1];		// 已求得的在最短路径上的顶点的顶点号
};

void dijkstra(struct graph * graph, int vi)
{
  int i, j;
  int pre;
  int min;
  int u, w;

  for (i = 1; i <= vertex; i++) {
    graph->dist[i] = graph->arcs[vi][i];
    graph->s[i] = 0;
    
    if ((i != vi) && (graph->dist[i] < max))
      graph->path[i] = vi;
    else
      graph->path[i] = 0;
  }

  graph->s[vi] = 1;
  graph->dist[vi] = 0;

  for (i = 1; i < vertex; i++) {
    min = max;
    u = vi;
    
    for (j = 1; j <= vertex; j++)	// 求最短路径
      if (!graph->s[j] && graph->dist[j] < min) {
	u = j;
	min = graph->dist[j];
      }
    
    graph->s[u] = 1;	// 将距离值最小的顶点并入集合S中

    for (w = 1; w <= vertex; w++)	// 修改路径长度
      if (!graph->s[w] && graph->arcs[u][w] < max && graph->dist[u] + graph->arcs[u][w] < graph->dist[w]) {
	graph->dist[w] = graph->dist[u] + graph->arcs[u][w];
	graph->path[w] = u;
      }
  }

  for (i = 1; i <= vertex; i++) {		// 输出路径长度及路径
    if (i != vi) {
      printf(" 1到 %d 最短距离:%d  %d", i, graph->dist[i], i);		// 输出终点

      pre = graph->path[i];
      while (pre != 0) {
	printf("  <----  %d ", pre);
	pre = graph->path[pre];
      }
      printf("\n");
    }
  }
}

void main()
{
  struct graph graph;
  int i, j, w, k;

  for (i = 1; i <= vertex; i++)
    for (j = 1; j <= vertex; j++)
      if (i == j)
	graph.arcs[i][j] = 0;
      else
	graph.arcs[i][j] = max;

  for (k = 1; k <= edge; k++) {
    printf("input edge and edge of quan value : \n");
    scanf("%d %d %d", &i, &j, &w);
    graph.arcs[i][j] = w;
  }

  dijkstra(&graph, 1);
}

